/*
 * @Author: liusheng
 * @Date: 2022-04-25 16:49:20
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-25 22:21:45
 * @Description: 剑指 Offer II 043. 往完全二叉树添加节点
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 043. 往完全二叉树添加节点
完全二叉树是每一层（除最后一层外）都是完全填充（即，节点数达到最大，第 n 层有 2n-1 个节点）的，并且所有的节点都尽可能地集中在左侧。

设计一个用完全二叉树初始化的数据结构 CBTInserter，它支持以下几种操作：

CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v)  向树中插入一个新节点，节点类型为 TreeNode，值为 v 。使树保持完全二叉树的状态，并返回插入的新节点的父节点的值；
CBTInserter.get_root() 将返回树的根节点。
 

示例 1：

输入：inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]]
输出：[null,1,[1,2]]
示例 2：

输入：inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出：[null,3,4,[1,2,3,4,5,6,7,8]]
 

提示：

最初给定的树是完全二叉树，且包含 1 到 1000 个节点。
每个测试用例最多调用 CBTInserter.insert  操作 10000 次。
给定节点或插入节点的每个值都在 0 到 5000 之间。
 

注意：本题与主站 919 题相同： https://leetcode-cn.com/problems/complete-binary-tree-inserter/
 */

/**
 * Your CBTInserter object will be instantiated and called as such:
 * CBTInserter* obj = new CBTInserter(root);
 * int param_1 = obj->insert(v);
 * TreeNode* param_2 = obj->get_root();
 */

 /*
 * Definition for a binary tree node.
*/
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

#include "header.h"

//traverse binary Tree By Level Solution
class CBTInserter {
public:
    CBTInserter(TreeNode* root) {
        this->root = root;
    }
    
    int insert(int v) {
        TreeNode * node = new TreeNode(v);
        //traverse by level,find the first null position to be insert
        queue<TreeNode *> levelNodes;
        levelNodes.push(root);

        while (!levelNodes.empty())
        {
            TreeNode * curNode = levelNodes.front();
            levelNodes.pop();
            if (curNode->left)
            {
                levelNodes.push(curNode->left);
            }
            else
            {
                curNode->left = node;
                return curNode->val;
            }

            if (curNode->right)
            {
                levelNodes.push(curNode->right);
            }
            else
            {
                curNode->right = node;
                return curNode->val;
            }
        }

        return 0;
    }
    
    TreeNode* get_root() {
        return root;
    }
private:
    TreeNode * root;
};

class CBTInserter2 {
public:
    CBTInserter2(TreeNode* root):root(root) {
        level = 1;

        queue<TreeNode *> tempLevel;
        tempLevel.push(root);
        //store TreeNode by level 
        while (!tempLevel.empty())
        {
            TreeNode * node = tempLevel.front();
            tempLevel.pop();

            levelNodes.push_back(node);

            if (node->left)
            {
                tempLevel.push(node->left);
            }

            if (node->right)
            {
                tempLevel.push(node->right);
            }
        }

        int allNums = (1 << level) - 1;
        while (allNums < levelNodes.size())
        {
            ++level;
            allNums = (1 << level) - 1;
        }
        // printf("level = %d\n",level);
    }
    
    int insert(int v) {
        TreeNode * node = new TreeNode(v);
        int levelMaxIndex = (1 << level) - 1;
        if (levelNodes.size() == levelMaxIndex)
        {
            ++level;
        }

        levelNodes.push_back(node);
        //parentNum start by 1
        int parentNum = levelNodes.size() / 2;
        if (levelNodes.size() % 2)
        {
            levelNodes[parentNum-1]->right = node;
        }
        else
        {
            levelNodes[parentNum-1]->left = node;
        }
        // printf("val:%d,parentIndex:%d\n",v,parentIndex);
        return levelNodes[parentNum-1]->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
private:
    TreeNode * root;
    //record the node by level
    //so the insert can manipulate by const time
    vector<TreeNode *> levelNodes;
    //current level
    int level;
};

/*
similar to solution2,not use the level
caculate the parent index through node vector size
*/
class CBTInserter3 {
public:
    CBTInserter3(TreeNode* root):root(root) {
        queue<TreeNode *> levelNodes;
        levelNodes.push(root);
        while (!levelNodes.empty())
        {
            TreeNode * curNode = levelNodes.front();
            levelNodes.pop();
            nodeByLevel.push_back(curNode);
            if (curNode->left)
            {
                levelNodes.push(curNode->left);
            }
            if (curNode->right)
            {
                levelNodes.push(curNode->right);
            }
        }
    }
    
    int insert(int val) {
        TreeNode * node = new TreeNode(val);
        nodeByLevel.push_back(node);
        int n = nodeByLevel.size();
        int parentIndex = (n - 2) / 2;
        //right
        if (n % 2 == 1)
        {
            nodeByLevel[parentIndex]->right = node;
        }
        else
        {
            nodeByLevel[parentIndex]->left = node;
        }
        
        return nodeByLevel[parentIndex]->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
private:
    TreeNode * root;
    vector<TreeNode *> nodeByLevel;
};

/*
use queue to record the not complete node
*/
class CBTInserter4 {
public:
    CBTInserter4(TreeNode* root):root(root) {
        //construct not complete node by level traverse
        queue<TreeNode *> nodesByLevel;
        nodesByLevel.push(root);
        while (!nodesByLevel.empty())
        {
            TreeNode * curNode = nodesByLevel.front();
            nodesByLevel.pop();
            //push the not complete node
            if (!curNode->left || !curNode->right)
            {
                nodesNotComplete.push(curNode);
            }

            if (curNode->left)
            {
                nodesByLevel.push(curNode->left);
            }

            if(curNode->right)
            {
                nodesByLevel.push(curNode->right);
            }
        }
    }
    
    int insert(int v) {
        TreeNode * node = new TreeNode(v);
        //parent is the first Node which not complete
        TreeNode * parent = nodesNotComplete.front();
        if (!parent->left)
        {
            parent->left = node;
        }
        else if(!parent->right)
        {
            parent->right = node;
            //now parent is a complete node,pop it 
            //from the queue
            nodesNotComplete.pop();
        }
        nodesNotComplete.push(node);
        
        return parent->val;
    }
    
    TreeNode* get_root() {
        return root;
    }
private:
    TreeNode * root;

    //record the not complete node in tree(not have two children)
    queue<TreeNode *> nodesNotComplete;
};
